package org.example.algorithm.linkedlist;

import java.util.List;
import java.util.PriorityQueue;

public class MergeKListsSolution {

    public static void main(String[] args) {
        ListNode list1 = new ListNode(1);
        list1.next = new ListNode(4);
        list1.next.next = new ListNode(5);
        ListNode list2 = new ListNode(1);
        list2.next = new ListNode(3);
        list2.next.next = new ListNode(4);
        ListNode list3 = new ListNode(2);
        list3.next = new ListNode(6);
        ListNode[] lists = new ListNode[3];
        lists[0] = list1;
        lists[1] = list2;
        lists[2] = list3;
        MergeKListsSolution solution = new MergeKListsSolution();
        ListNode ans = solution.mergeKLists(lists);
    }

    //分治合并
    public ListNode mergeKLists(ListNode[] lists) {
        return doMerge(lists, 0, lists.length-1);
    }

    private ListNode doMerge(ListNode[] lists, int start, int end) {
        if (start == end) {
            return lists[start];
        }
        if (start > end) {
            return null;
        }
        int mid = (start + end) >> 1;
        return merge2List(doMerge(lists, start, mid), doMerge(lists, mid+1, end));
    }

    private ListNode merge2List(ListNode listNode1, ListNode listNode2) {
        ListNode cur1 = listNode1;
        ListNode cur2 = listNode2;
        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        while (cur1!=null && cur2!=null) {
            if (cur1.val > cur2.val) {
                tail.next = cur2;
                cur2 = cur2.next;
            } else {
                tail.next = cur1;
                cur1 = cur1.next;
            }
            tail = tail.next;
        }
        tail.next = cur1 == null ? cur2 : cur1;
        return dummy.next;
    }

    //使用最小堆
    public ListNode mergeKLists1(ListNode[] lists) {
        int len = lists.length;
        if (len == 0) {
            return null;
        }
        PriorityQueue<ListNode> queue = new PriorityQueue<>((a,b) -> a.val - b.val);
        for (int i=0;i<len;i++) {
            if (lists[i] != null) {
                queue.offer(lists[i]);
            }
        }
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        while (!queue.isEmpty()) {
            ListNode tempNode = queue.poll();
            if (tempNode.next != null) {
                queue.offer(tempNode.next);
            }
            cur.next = tempNode;
            cur = cur.next;
        }
        return dummy.next;
    }

    //O(n*k)
    public ListNode mergeKLists2(ListNode[] lists) {
        int len = lists.length;
        if (len == 0) {
            return null;
        }
        ListNode[] curArr = new ListNode[len];
        for (int i=0;i<len;i++) {
            curArr[i] = lists[i];
        }
        ListNode ans = new ListNode();
        ListNode ansCur = ans;
        while (true) {
            int min = Integer.MAX_VALUE;
            for (int i=0;i<len;i++) {
                if (curArr[i] != null && curArr[i].val < min) {
                    min = curArr[i].val;
                }
            }
            if (min == Integer.MAX_VALUE) {
                break;
            }
            for (int i=0;i<len;i++) {
                if (curArr[i] != null && curArr[i].val == min) {
                    ansCur.next = curArr[i];
                    ansCur = ansCur.next;
                    curArr[i] = curArr[i].next;
                }
            }
        }
        return ans.next;
    }
}
